# -*- coding: utf-8 -*-

"""221. 最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出：4

示例 2：
输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：
输入：matrix = [["0"]]
输出：0

提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'"""

class Solution:
    """
    这道题的难点还是在于怎么定义正方形，按照拼凑法来说，取每行来说，每个位置底为1的柱子高度
    ---------  ---------  ---------  ---------
    1 0 1 0 0  2 0 2 1 1  3 1 3 2 2  4 0 0 3 0
    ---------  ---------  ---------  ---------
    第一行      第二行      第三行      第四行

    然后看每行，比如第三行
    有三种高度的柱子 1，2，3
    高度大于等于 1 的最大连续柱子有 5 根，可凑成 1*1 的正方形
    高度大于等于 2 的最大连续柱子有 3 根，可凑成 2*2 的正方形
    高度大于等于 3 的最大连续柱子有 1 根，可凑成 1*1 的正方形
    所以这行的最大正方形为 2*2

    最后把每一行计算之后取最大的正方形。

    实现具体算法时，可以将这些过程切面合在一起，封装成整体，不可分解。

    -----------------------------
    看题解，可用动态规划来解。先用计算过程的递归，定义 f(m,n) 为求以位置 (m,n) 处为正方形的右下角的最大正方形。
    则递归基础：
    f(1, i) = 1 or 0
    f(i, 1) = 1 or 0 
    递归运算:
    f(m,n) = min(f(m, n-1), f(m-1, n), f(m-1, n-1))+1       # 当matrix(m,n) = 1，直观地理解就是像木匠那个直尺去框一个正方形
    f(m,n) = 0                                              # 当matrix(m,n) = 0
    将递归运算过程按动态规划转化为递推状态缓存。
    """
    def maximalSquareChart(self, matrix: list) -> int:
        high = [0 for _ in matrix[0]]
        s = len(high)
        square = 0

        for row in matrix:
            # 以本行为底的柱子
            i = 0
            while i < s:
                if row[i] == '1':
                    high[i] += 1
                else:
                    high[i] = 0
                i += 1
            # print(high)

            for h in set(high):
                if h == 0:
                    continue
                # 柱子高大于等于 h 的最大连续柱子
                count, maxcount = 0, 0
                i = 0
                while i < s:
                    if high[i] >= h:
                        count +=1
                    else:
                        maxcount = max(maxcount, count)
                        count = 0
                    i += 1
                maxcount = max(maxcount, count)
                # 柱子高为 h 的最大面积
                edge = min(h, maxcount)
                square = max(square, edge * edge)

        return square
    
    def maximalSquare(self, matrix: list) -> int:
        row, col = len(matrix), len(matrix[0])
        dp = []
        i = 0
        while i < row:
            dp.append([int(v) for v in matrix[i]])
            i += 1

        i = 1
        while i < row:
            j = 1
            while j < col:
                if dp[i][j] == 1:
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1
                j += 1
            i += 1
        # print(dp)

        edge = 0
        i = 0
        while i < row:
            j = 0
            while j < col:
                edge = max(edge, dp[i][j])
                j += 1
            i += 1

        return edge * edge

if __name__ == '__main__':
    print(Solution().maximalSquare([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]))
